#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void test1(){
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);

    for (int i = 0; i < v.size(); ++i) {
        cout << v[i] << " ";
    }
    cout << endl;
    for (auto p : v) {
        cout << p << " ";
    }
    cout << endl;
    vector<int>::iterator pc = v.begin();
    while (pc != v.end()){
        (*pc) += 1;
        cout << *pc << " ";
        ++pc;
    }
}

void test2(){
    vector<int> v(10,1);
    for (auto p:v) {
        cout << p << " ";
    }
    cout << endl;
    vector<int> v2(v.begin(),v.end()-5);
    for (auto p:v2) {
        cout << p << " ";
    }
    cout << endl;
    string s("hello chongqing");
    vector<char> v3(s.begin()+3,--s.end());
    for (auto p:v3) {
        cout << p << " ";
    }
    cout << endl;
}

void test3(){
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    auto pc = v.begin();
    while (pc != v.end()){
        cout << *pc << " ";
        ++pc;
    }
    cout << endl;
    auto rpc = v.rbegin();
    while (rpc != v.rend()){
        cout << *rpc << " ";
        ++rpc;
    }
    cout << endl;
}

void test4(){
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    for (auto pc : v) {
        cout << pc << " ";
    }
    cout << endl;
    vector<int>::iterator pos = find(v.begin(),v.end(),2);
    if (pos != v.end())
        v.insert(pos,66);
    for (auto pc : v) {
        cout << pc << " ";
    }
    cout << endl;
    pos = find(v.begin(),v.end(),2);
    if (pos != v.end())
        v.erase(pos);
    for (auto pc : v) {
        cout << pc << " ";
    }
    cout << endl;
    v.erase(v.begin());
    for (auto pc : v) {
        cout << pc << " ";
    }
    cout << endl;
}

//136. 只出现一次的数字
//https://leetcode.cn/problems/single-number/

/*
class Solution {
public:
    static int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto it : nums) {
            ret ^= it;
        }
        return ret;
    }
};
*/

//118. 杨辉三角
//https://leetcode.cn/problems/pascals-triangle/description/

/*
class Solution {
public:
    static vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vv;
        vv.resize(numRows,vector<int>());
        for (int i = 0; i < vv.size(); ++i) {
            vv[i].resize(i + 1, 0);
            vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        }
        for (int i = 0; i < vv.size(); ++i) {
            for (int j = 0; j < vv[i].size(); ++j) {
                if (vv[i][j] == 0)
                    vv[i][j] = vv[i-1][j] + vv[i-1][j-1];
            }
        }
        return vv;
    }
};
*/

//17. 电话号码的字母组合
//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

/*
class Solution {
    vector<string> numToStr = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void Combinations(const string& digits, size_t di, string combineStr, vector<string>& strV){
        if (di == digits.size()){
            strV.push_back(combineStr);
            return;
        }
        int num = digits[di] - '0';
        string str = numToStr[num];
        for (auto ch : str) {
            Combinations(digits, di + 1, combineStr + ch, strV);
        }
    }
public:
    vector<string> letterCombinations(const string& digits) {
        vector<string> strV;
        if (digits.empty())
            return strV;
        Combinations(digits, 0, "",strV);
        return strV;
    }
};

void Test1(){
    string digits = "23";
    vector<string> ret = Solution().letterCombinations(digits);
    for (auto & i : ret) {
        cout << i << endl;
    }
}

int main() {
    //test2();
    Test1();
    return 0;
}
*/

/*
int main(){
    vector<int>array;
    array.push_back(100);
    array.push_back(300);
    array.push_back(300);
    array.push_back(300);
    array.push_back(300);
    array.push_back(500);
    vector<int>::iterator itor;
    for(itor=array.begin();itor!=array.end();itor++)
    {
        if(* itor==300)
        {
            itor=array.erase(itor);
        }
    }
    for(itor=array.begin();itor!=array.end();itor++)
    {
        cout<<*itor<<" ";
    }
    return 0;
}
*/

//137. 只出现一次的数字 II
//https://leetcode.cn/problems/single-number-ii/

/*
class Solution {
public:
    static int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int j = 0; j < nums.size(); ++j) {
                total += ((nums[j] >> i) & 1);
            }
            if (total % 3)
                ret |= (1 << i);
        }
        return ret;
    }
};

int main(){
    vector<int> tmp = {2,3,4,3,4,2,2,5,3,4};
    cout << Solution::singleNumber(tmp) << endl;
    return 0;
}
*/

//260. 只出现一次的数字 III
//https://leetcode.cn/problems/single-number-iii/

class Solution {
public:
    static vector<int> singleNumber(vector<int>& nums) {
        int xorRet = 0;
        for (int num : nums) {
            xorRet ^= num;
        }
        int k = -1;
        for (int i = 0; i < 32 && k == -1; ++i) {
            if (((xorRet >> i) & 1) == 1)
                k = i;
        }
        vector<int> ret = {0,0};
        for (int num : nums) {
            if (((num >> k) & 1) == 1)
                ret[1] ^= num;
            else
                ret[0] ^= num;
        }
        return ret;
    }
};

int main(){
    vector<int> tmp = {1,2,3,4,3,2,1,5,5,6};
    for (int num : Solution::singleNumber(tmp)) {
        cout << num << ' ';
    }
    return 0;
}